package slist;
import java.util.List;

public class MySingleList {

        static class ListNode {
            public int val;//节点的值域
            public ListNode next;//下一个节点的地址

            public ListNode(int val) {
                this.val = val;
            }

        }


        public ListNode head;//表示当前链表的头节点

        public void createList() {

            ListNode node1 = new ListNode(12);
            ListNode node2 = new ListNode(23);
            ListNode node3 = new ListNode(34);
            ListNode node4 = new ListNode(45);
            ListNode node5 = new ListNode(56);

            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;

            this.head = node1;

        }

        public void display() {
            ListNode cur = head;
            while (cur != null) {
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }

        //得到单链表的长度
        public int size(){
            int count = 0;
            ListNode cur = head;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }

        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            ListNode cur = head;
            while (cur != null) {
                if(cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }


        //头插法
        public void addFirst(int data){
            ListNode node = new ListNode(data);
            node.next = head;
            head = node;
        }


        //尾插法
        public void addLast(int data){
            ListNode node = new ListNode(data);
            ListNode cur = head;
            if(cur == null) {
                head = node;
                return;
            }
            //找到链表的尾巴  注意是cur.next 不是cur
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }

        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
            if(index < 0 || index > size()) {
                System.out.println("index 不合法");
                return;
            }
            if(index == 0) {
                addFirst(data);
                return;
            }
            if(index == size()) {
                addLast(data);
                return;
            }
            ListNode cur = findIndexSubOne(index);
            ListNode node = new ListNode(data);
            node.next = cur.next;
            cur.next = node;
        }

        /**
         * 找到要删除节点位置的前一个节点
         * @param index
         * @return
         */
        private ListNode findIndexSubOne(int index) {
            ListNode cur = head;
            while (index-1 != 0) {
                cur = cur.next;
                index--;
            }
            return cur;
        }



        //删除第一次出现关键字为key的节点
        public void remove(int key){
            if(head == null) {
                return;
            }
            //单独删除头节点
            if(head.val == key) {
                head = head.next;
                return;
            }
            ListNode cur = searchPrev(key);
            if(cur == null) {
                System.out.println("没有你要删除的数字");
                return;
            }
            ListNode del = cur.next;
            cur.next = del.next;
        }

        /**
         * 找到关键字 key的前驱
         * @param key
         * @return
         */
        private ListNode searchPrev(int key) {
            ListNode cur = head;
            while (cur.next != null) {
                if(cur.next.val == key) {
                    return cur;
                }
                cur = cur.next;
            }
            return null;
        }

        //删除所有值为key的节点
        public void removeAllKey(int key) {
            if (head == null) {
                return;
            }

            ListNode cur = head.next;
            ListNode prev = head;

            while (head.val == key) {
                head = head.next;
                cur = head.next;
                prev = head;
            }

            while (cur != null) {
                if (cur.val == key) {
                    prev.next = cur.next;
                    cur = cur.next;
                } else {
                    prev = cur;
                    cur = cur.next;
                }
            }
        }

        //清空链表
        public void clear() {
            this.head = null;
        }
}
